package com.cheng.algorithm.sort;

import java.util.Arrays;

/**
 * @User Administrator
 * @Classname QuickSort
 * @Project Data-structure-and-algorithm
 * @Description 快速排序（Quicksort）是对冒泡排序的一种改进。
 * 基本思想是:通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，
 * 然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列
 * @Author wpcheng
 * @Create 2021-08-07-8:43
 * @Version 1.0
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {-9,78,0,23,-100,-2,70};
        quickSort(arr,0, arr.length-1);
        System.out.println(Arrays.toString(arr));
    }

    /**
     *
     * @param arr 要进行快速排序的数组
     * @param left 指向数组最左边的下标 0
     * @param right 指向数组最右边的下标 arr.length-1
     */
    public static void quickSort(int[] arr,int left,int right){
        //记录两个下标
        int l = left;
        int r = right;
        int pivot = arr[(left + right) / 2]; //找到数组中轴的那个数,以中轴为界线，划分成左右两个数组，左数小于等于中轴，右边的数大于等于中轴
        int temp = 0;
        //当这个循环完成时，就实现了左边数小于等于中轴，右边的数大于等于中轴
        while (l < r){
            //从中轴最左边向中轴方向开始循环遍历，直到找到大于等于中轴数的数字，就退出循环
            while (arr[l] < pivot){
                l++;
            }
            //从中轴最右边向中轴方向开始循环遍历，直到找到小于等于中轴数的数字，就退出循环
            while (arr[r] > pivot){
                r--;
            }

            //当上面两个循环退出后，就把找到的两个数进行交换
            temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;

            //如果l >= r，说明已经遍历完成
            if (l >= r){
                break;
            }

            //如果交换完，发现右边的数arr[l] == 中轴数pivot，这个数无需比较
            if (arr[l] == pivot){
                l--;//就让l前移,比较下一个即可
            }
            //如果交换完，发现左边的数arr[r] == 中轴数pivot，这个数无需比较
            if (arr[r] == pivot){
                r--;//就让r后移,比较下一个即可
            }
        }

        //如果l == r，就让两个错位
        if (l == r){
            l++;
            r--;
        }
        //向左递归
        if (left < r){
            quickSort(arr,left,r);
        }
        //向右递归
        if (right > l){
            quickSort(arr,l,right);
        }











    }





}

